package de.herberlin.server.httpd.ssi;

import java.io.*;

/** Expr.java
 *	Simple recursive parser for Expressions.
 *	Tries to follow the standards of gnu expr,
 *	but does not understand regular expressions.
 *	I found it usefull to have a lightwight replacement
 *	for the gnu.expr.Parser to use with java code.
 *
 * Copyright (C) March 25, 2002 author Hans Joachim Herbertz.
 * www.herberlin.de
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.*/
public class Expr {
    /** Debug flag  */
    public static final boolean DEBUG=false;
    /** Version string */
    public static final String VERSION="de.herberlin.util.Expr version 1.0";
    
    /** Definition of operations */
    private final String[][] operation= new String[][] {
        {"\"","[","]"},	// unsupported operations
        {"||","|","&&","&"},
        {"==","!=",">=","<=",">","<","="},
        {"+","-"},
        {"*","/","%"},
        {"!"}
    };
    /** Numbers for identifying operations */
    private final int[][] operationNumber=new int[][] {
        {0,0,0},
        {3,3,4,4},
        {5,6,7,8,9,10,5},
        {11,12},
        {13,14,16},
        {15}
    };
    /**
     *	Class representing a logical or arethmetical operation */
    class Operation {
        /** Position of the operation symbol in expression string*/
        public int position=-1;
        /** String representation of the operation*/
        public String sign="";
        /** Length of the operation sign, for example "=" is 1 and "<=" is 2. */
        public int length=1;
        /** Operation number */
        public int opNumber=0;
        /** String representation of the class */
        public String toString() { return "Position: "+position+" Sign: "+sign;};
    }
    
    /**
     *	Class represention braces of an expression */
    class Braces {
        /** Opening braces position */
        private int startPos=-1;
        /** Closing braces position */
        private int endPos;
        /** Further braces in the expression */
        private Braces moreBraces=null;
        /* Constructor for the first braces in an expression */
        public Braces(String expr) throws ExprException {
            init(expr,0);
        }
        /** constructor for further braces in an expression */
        public Braces(String expr,int startPosition) throws ExprException {
            init(expr,startPosition);
        }
        /** Initialization of data callen by constructor.*/
        private void init(String expr,int startPosition) throws ExprException {
            if (Expr.DEBUG) trace("Braces",expr+" "+startPosition);
            if (expr==null) {
                if (Expr.DEBUG) trace("Braces return ","null");
                return;
            }
            if ((startPos=expr.indexOf("(",startPosition))<0) {
                if (Expr.DEBUG) trace("Braces","-1");
                return;
            }
            int bracesCounter=1;
            for (int i=startPos+1;i< expr.length();i++) {
                if (expr.substring(i,i+1).equals("(")) bracesCounter++;
                if (expr.substring(i,i+1).equals(")")) bracesCounter--;
                if (bracesCounter==0) {
                    endPos=i;
                    break;
                }
            }
            if (bracesCounter!=0) throw new ExprException(" Braces missing: "+expr);
            if (startPos>-1 && endPos+1<expr.length()) moreBraces=new Braces(expr,endPos);
            if (Expr.DEBUG) trace("Braces",startPos+" "+endPos);
        }
        /** Finds out if a position is outside the braces of the expression.
         *	@param pos the position to examine.
         *	@return true if pos is outside all braces of the expression, else false */
        public boolean isOutside(int pos) {
            if (Expr.DEBUG) trace("Braces#isOutside",pos+" ");
            if ( startPos<0) {
                if (Expr.DEBUG) {trace("Braces#isOutside return=","true");}
                return true; // no braces
            }
            if ( (pos>startPos) && (pos<endPos) ) {
                if (Expr.DEBUG) {trace("Braces#isOutside return=","false");}
                return false;
            }
            if (moreBraces!=null) {
                boolean ret=moreBraces.isOutside(pos);
                if (Expr.DEBUG) trace("Braces#isOutside return=",new Boolean(ret).toString());
                return ret;
            }
            if (Expr.DEBUG) {trace("Braces#isOutside return=","true");}
            return true;
        }
        /**	Indicates if the braces surround the whole expression.
         *	@param expr the expression to test
         *	@return true if braces surround the whole string */
        public boolean borderBraces(String expr) {
            boolean ret=false;
            if (startPos==0 && endPos== expr.length()-1) ret= true;
            if (DEBUG) trace("Braces#borderBraces("+expr+") return =",""+ret);
            return ret;
        }
    }
    
    /** For debugging*/
    protected static void trace(String function,String params) {
        System.out.println(function+" "+params);
    }
    /**	An expression is a Token if no more operations can be performed
     *	@param expr an expression
     *	@return true if the expression is a token.
     *	@see Token class Token			*/
    private boolean isToken(String expr) {
        if (Expr.DEBUG) trace("isToken",expr);
        for (int j=0;j<operation.length;j++) {
            for (int i=0;i<operation[j].length;i++) {
                if ( expr.indexOf(operation[j][i])> -1) {
                    if (DEBUG) {trace("isToken return=","false");}
                    return false;
                }
            }
        }
        if (DEBUG) {trace("isToken return=","true");}
        return true;
    }
    /** Finds the highes ranking operation to perform. Raking and
     *	operations are defined in private final String[][] Expr#operation.
     *	Only operations outside braces are regarded.
     *	@param expr The expression to parse.
     *	@return Operation Operation
     *	@exception ExprException if a parser error occures.*/
    private Operation findHight(String expr) throws ExprException {
        
        if (Expr.DEBUG) Expr.trace("findHight",expr);
        
        int ret=-1;
        int current=-1;
        Braces br=new Braces(expr);
        Operation op=new Operation();
        for (int j=0;j<operation.length;j++) {
            for (int i=0;i<operation[j].length;i++) {
                current=expr.indexOf(operation[j][i]);
                if (current>-1 && (current >= ret+op.length) && br.isOutside(current)) {
                    ret=current;
                    op.position=ret;
                    op.sign=operation[j][i];
                    op.length=operation[j][i].length();
                    op.opNumber=operationNumber[j][i];
                }
            }
            if (ret>-1) {
                if (DEBUG) trace("findHight return=",op.sign);
                return op;
            }
        }
        if (DEBUG) trace("findHight return=","null");
        return null;
    }
    /** Removes surrounding braces.
     *	@param expr an expression to parse
     *	@return The parsed expression
     *	@exception ExprException if a parser error occures.*/
    private String removeBraces(String expr)throws ExprException {
        if (Expr.DEBUG) trace("removeBraces",expr);
        Braces br=new Braces(expr);
        while (br.borderBraces(expr)) {
            expr=expr.substring(1,expr.length()-1);
            br=new Braces(expr);
        }
        if (Expr.DEBUG) trace("removeBraces return=",expr);
        return expr;
    }
    /** The recursive parser.
     *	@param expr an expression to parse
     *	@return The parsed expression
     *	@exception ExprException if a parser error occures.*/
    private String parseIt(String expr)throws ExprException {
        if (Expr.DEBUG) trace("parseIt",expr);
        expr=removeBraces(expr);
        Operation op=findHight(expr);
        if (op==null) {
            Token t=new Token(expr);
            if (Expr.DEBUG) trace("parseIt return=",t.boolValue+"");
            return t.boolValue+"";
        }
        
        String first=expr.substring(0,op.position);
        String second=expr.substring(op.position+op.length);
        
        if (!isToken(first)) first=parseIt(first);
        if (!isToken(second)) second= parseIt(second);
        
        Token t1=new Token(removeBraces(first));
        Token t2=new Token(removeBraces(second));
        String result="";
        
        switch (op.opNumber) {
            case 0: // invalid signs
                throw new ExprException(op.sign+" in "+expr);
            case 3: // ||
                result= new Boolean(t1.boolValue || t2.boolValue).toString() ;
                break;
            case 4: // &&
                result= new Boolean(t1.boolValue && t2.boolValue).toString() ;
                break;
            case 5: // ==
                if (t1.isNumber && t2.isNumber) result=new Boolean(t1.numberValue== t2.numberValue).toString();
                else result= new Boolean(t1.sign.equals(t2.sign)).toString();
                break;
            case 6: // !=
                if (t1.isNumber && t2.isNumber) result=new Boolean(t1.numberValue!= t2.numberValue).toString();
                else result= new Boolean(!t1.sign.equals(t2.sign)).toString();
                break;
            case 7: // >=
                if (t1.isNumber && t2.isNumber) result=new Boolean(t1.numberValue>= t2.numberValue).toString();
                else result=new Boolean( 0<=t1.sign.compareTo(t2.sign)).toString();
                break;
            case 8: // <=
                if (t1.isNumber && t2.isNumber) result=new Boolean(t1.numberValue<= t2.numberValue).toString();
                else result=new Boolean( 0>=t1.sign.compareTo(t2.sign)).toString();
                break;
            case 9: // >
                if (t1.isNumber && t2.isNumber) result=new Boolean(t1.numberValue> t2.numberValue).toString();
                else result=new Boolean( 0<t1.sign.compareTo(t2.sign)).toString();
                break;
            case 10: // <
                if (t1.isNumber && t2.isNumber) result=new Boolean(t1.numberValue< t2.numberValue).toString();
                else result=new Boolean( 0>t1.sign.compareTo(t2.sign)).toString();
                break;
            case 11: // +
                if (t1.isNumber && t2.isNumber) result =new Double(t1.numberValue+t2.numberValue).toString();
                else throw new ExprException(t1.sign+" + "+t2.sign);
                break;
            case 12: // -
                if (t1.isNumber && t2.isNumber) result =new Double(t1.numberValue-t2.numberValue).toString();
                else throw new ExprException(t1.sign+" - "+t2.sign);
                break;
            case 13: // *
                if (t1.isNumber && t2.isNumber) result =new Double(t1.numberValue*t2.numberValue).toString();
                else throw new ExprException(t1.sign+" * "+t2.sign);
                break;
            case 14: // /
                if (t1.isNumber && t2.isNumber) result =new Double(t1.numberValue/t2.numberValue).toString();
                else throw new ExprException(t1.sign+" / "+t2.sign);
                break;
            case 15: // !
                result=new Boolean(!t2.boolValue).toString();
                break;
            case 16: // %
                if (t1.isNumber && t2.isNumber) result =new Double(t1.numberValue%t2.numberValue).toString();
                else throw new ExprException(t1.sign+" % "+t2.sign);
                break;
                
        }
        if (Expr.DEBUG) trace("parseIt return=",result);
        return result;
    }
    
    /** The parser java interface.
     *	@param expression an expression to parse
     *	@return true if the parser result is true, else false.
     *	@exception ExprException if a parser error occures.*/
    public static boolean parse(String expression) throws ExprException {
        
        Expr myExpr=new Expr();
        return new Token(myExpr.parseIt(expression)).boolValue;
    }
    
    /**	Some expressions to test how the parser works
     *	@return String the test logs.	*/
    private static String test() {
        String[] tests=new String[] {
            "true",
            "false",
            "aString",
            "!aString",
            "",
            "1",
            "2",
            "0",
            "-1",
            "!-1",
            "!(-1)",
            "eins == eins",
            "eins == Eins",
            "eins ==1",
            "123 = 123",
            "3 !=4",
            "one!=two",
            "one!=one",
            "1!=one",
            "2>=4",
            "4>=3",
            "drei>=3",
            "drei>=dreizehn",
            "2>-33",
            "2<4",
            "4<=4",
            "drei<=3",
            "drei<=dreizehn",
            "true || true && false",
            "true || (true && false) ",
            "true | (true & false) ",
            "3+2==5",
            "7*7",
            "3*4-12==0",
            "12-3*4+2!=2",
            "2/2==1",
            "2%3=2",
            "3*(4-12)==-24",
            "((3+3)-1)/(-1)=(-5)",
            "!(0)==true"
        };
        StringBuffer result=new StringBuffer();
        for (int i=0;i<tests.length;i++) {
            result.append(tests[i]+"\t=> ");
            try {
                result.append(Expr.parse(tests[i]));
            }catch (ExprException e) {
                result.append(e.getMessage());
            }
            result.append("\n");
        }
        return result.toString();
    }
    /** Prints usage informations.*/
    public static void printUsage() {
        String[] usage=new String[] {
            VERSION,
            "",
            "Usage: java de.herberlin.util.Expr",
            "\t-t\tshows examples.",
            "\t-h\tshows this help.",
            "\taString\tparses expression.",
            "",
            "\tYou can use Expr with pipes for example:",
            "\techo 3+3=6 | java de.herberlin.util.Expr",
            "",
            "The parser does not understand regular expressions.",
            "If the expression can be parsed, it returns true or false,",
            "else an error message is shown.",
            "",
            "To use this class from other java programs, the interface is:",
            "\tpublic static boolean de.herberlin.util.Expr.parse(String)",
            "\t  throws de.herberlin.util.ExprException"
        };
        for (int i=0;i<usage.length;i++) System.out.println(usage[i]);
    }
    
    /** Application run method */
    public static void main(String[] argv) {
        
        // Checking for stream at std.in
        int available=0;
        try {
            available=System.in.available();
        } catch (IOException io) {};
        
        if (available!=0) {
            // if stream at std.in parse stream
            BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
            String t;
            try {
                while ( (t=in.readLine()) !=null) {
                    try {
                        System.out.println(Expr.parse(t));
                    } catch (ExprException ex) {
                        System.out.println(t+"\t=> "+ex.getMessage());
                    }
                }
            } catch (IOException io) {
                System.err.println(io.getMessage());
            }
        }else if (argv.length==0 || argv[0].indexOf("-h") ==0) {
            // usage
            printUsage();
        } else if (argv[0].indexOf("-t")==0) {
            // testing system
            System.out.println(test());
        } else {
            // parse argv
            for(int i=0;i<argv.length;i++) {
                try {
                    System.out.println(Expr.parse(argv[i]));
                } catch (ExprException e) {
                    System.out.println(e.getMessage());
                }
            } //~ for
        } //~ if
    } //~ main
} //~ class

/** A Token represents an element of an expression that cant be
 *	parsed into an operation therefore an operation are to be performed
 *	on it. A Token has a String and a Boolean representation; it also my
 *	have a Number representation. */
class Token {
    /** String representation of the Token */
    public String sign="";
    /** Indicates wether the Token is numeric so
     *	arithmetic operations may be performed on it.*/
    public boolean isNumber=false;
    /** Numeric representation of the Token*/
    public double numberValue=0;
    /** Boolean representation of the Token.*/
    public boolean boolValue=true;
    /**	Constructor; initiates values.
     *	Please note: An empty String is treated as:
     *	sign="",isNumber=true,numberValue=0,booleanValue=false. */
    public Token(String aSign) {
        if (Expr.DEBUG) Expr.trace("Token",aSign);
        this.sign=aSign.trim();
        try {
            numberValue= Double.valueOf(sign).doubleValue();
            isNumber=true;
        } catch (Exception e) {;}
        // workaround for negative values
        if (sign.length()==0) {
            isNumber=true;
            numberValue=0;
        }
        // boolValue
        if ( 	(isNumber==true && numberValue==0)
        || 	(sign.equals("false")) ) {
            
            boolValue=false;
        }
        if (Expr.DEBUG) {Expr.trace("Token",toString());}
    }
    /** String representation of the class */
    public String toString() {
        return sign+" isNumber="+isNumber+" boolValue="+boolValue;
    }
}

